package com.lry.basic.algorithm.dp;

class GridGame {
    public static void main(String[] args) {
        System.out.println(gridGame2(new int[][]{{2,5,4}, {1,5,1}}));
    }


    public static long gridGame(int[][] grid) {
        int min = Integer.MAX_VALUE;

        int sum1 = 0;
        int sum2 = 0;

        for(int j=0;j<grid[0].length;j++){

            for(int col=j+1;col<grid[0].length;col++){
                sum1+=grid[0][col];
            }
            for(int col=0;col<j;col++){
                sum2+=grid[1][col];
            }
            int max = Math.max(sum1,sum2);

            if(max<min){
                min = max;
            }
            sum1 = 0;
            sum2 = 0;
        }

        return min;

    }

    public static long gridGame2(int[][] grid) {
        long[][] dp = new long[grid.length][grid[0].length];

        dp[0][0] = grid[0][0];
        dp[1][0] = grid[1][0];

        for(int j= 1;j<grid[0].length;j++){

            dp[0][j] = dp[0][j-1] + grid[0][j];

            dp[1][j] = dp[1][j-1] + grid[1][j];
        }

        long min = Long.MAX_VALUE;
        for(int j=0;j<grid[0].length;j++){
            long max = Math.max(dp[0][dp[0].length-1]-dp[0][j], j-1>=0?dp[1][j-1]:0);
            if(min>max){
                min = max;
            }
        }
        return min;
    }
}